package com.leetcode.leetcode2;

/**
 * 最长回文子序列
 *
 * @author luhd
 * @date 2023-08-01
 */
public class Practice516 {
    /**
     * 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
     *
     * 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
     * 输入：s = "bbbab"
     * 输出：4
     * 解释：一个可能的最长回文子序列为 "bbbb" 。
     */
    public static void main(String[] args) {
        // String s = "bbbab";
        String s = "cbbd";
        System.out.println(longestPalindromeSubseq(s));
    }

    public static int longestPalindromeSubseq(String s) {
        // 获取字符串 s 的长度
        int length = s.length();

        // 设置数组 dp，用来存储字符串 s 的最长的回文子序列的长度
        // dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的最长的回文子序列的长度
        // dp[2][3] 表示字符串 s 第 2 个字符和字符串 s 第 3 个字符之间的最长的回文子序列的长度
        // dp[i][j] 表示字符串 s 第 i 个字符和字符串 s 第 j 个字符之间的最长的回文子序列的长度
        // i 最大值为 length - 1
        int[][] dp = new int[length][length];

        // dp[0][0] 表示字符串 s 第 0 个字符和字符串 s 第 0 个字符之间的最长的回文子序列的长度
        // dp[3][3] 表示字符串 s 第 3 个字符和字符串 s 第 3 个字符之间的最长的回文子序列的长度
        // dp[i][i] 表示字符串 s 第 i 个字符和字符串 s 第 i 个字符之间的最长的回文子序列的长度
        // 此时，这个区间的字符只有一个，最长的回文子序列的长度为 1
        for (int i = 0; i < length; i++) {
            dp[i][i] = 1;
        }

        for (int i = length - 1; i >= 0; i--) {
            for (int j = i+1; j < length; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1] +2;
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][length-1];

        // i 从字符串 s 的【尾部】开始向前遍历，j 从 i + 1 开始向后遍历
        // 不断的逼近二维数组最右上角的位置，即求 dp[0][length - 1]
        /*for (int i = length - 1; i >= 0; i--) {

            for( int j = i + 1 ; j < length ; j++ ){

                // 如果发现 s.charAt(i) == s.charAt(j)
                if (s.charAt(i) == s.charAt(j)) {

                    // dp[i][j] 表示字符串 s 第 i 个字符和字符串 s 第 j 个字符之间的最长的回文子序列的长度
                    // dp[i][j] 表示字符串 s 第 i + 1 个字符和字符串 s 第 j - 1 个字符之间的最长的回文子序列的长度
                    // 由于扩充的两个字符相等，意味着最长的回文子序列的长度加 2
                    dp[i][j] = dp[ i + 1 ][ j - 1 ] + 2;

                }else{

                    // 字符区间 s[i..j] 里最长回文子序列的长度
                    // 1、去掉头以后的区间的最长的回文子序列的长度，即 dp[i + 1][j]
                    // 2、去掉尾以后的区间的最长的回文子序列的长度，即  dp[i][j - 1]
                    // 二者取最大值
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }

        }

        // 最右上角的值就是结果
        return dp[0][length - 1];*/
    }
}